//
// Created by xili on 2024/9/21 16:44.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution1 {
public:
    int combinationSum4(vector<int> &nums, int target) {
        return f(nums, target);
    }

    int f(vector<int> &nums, int cur) {
        if (cur == 0) {
            return 1;
        }
        if (cur < 0) {
            return 0;
        }
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            ans += f(nums, cur - nums[i]);
        }
        return ans;
    }
};

//记忆化搜索
class Solution2 {
public:
    int combinationSum4(vector<int> &nums, int target) {
        vector<int> dp(target + 1, -1);
        return f(nums, target, dp);
    }

    int f(vector<int> &nums, int cur, vector<int> &dp) {
        if (cur == 0) {
            return 1;
        }
        if (cur < 0) {
            return 0;
        }
        if (dp[cur] != -1) {
            return dp[cur];
        }
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            ans += f(nums, cur - nums[i], dp);
        }
        dp[cur] = ans;
        return ans;
    }
};

//严格位置依赖
class Solution3 {
public:
    int combinationSum4(vector<int> &nums, int target) {
        int n = nums.size();
        vector<unsigned> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < n; j++) {
                dp[i] += i - nums[j] >= 0 ? dp[i - nums[j]] : 0;
            }
        }
        return dp[target];
    }
};